/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-10-13
 * Time:9:29
 */
public class MyList {
    static class List{
        public int val;
        //next
        public List(int val) {
            this.val = val;
        }
        public List next;
    }
    public List head;
    public void creat(){
        List list1=new List(1);
        List list2=new List(2);
        List list3=new List(3);
        List list4=new List(4);
        List list5=new List(5);

        this.head=list1;
        list1.next=list2;
        list2.next=list3;
        list3.next=list4;
        list4.next=list5;
    }
    //头插法
    public void addFirst(int data){
        List list=new List(data);
        list.next=head;
        this.head=list;

    }
    //尾插法
    public void addLast(int data){
        List cur =head;
        if(cur==null){
            head.val=data;
        }else {
            List node=new List(data);
            while(cur.next!=null){
                cur=cur.next;
            }
            cur.next=node;
        }
    }

    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        //前面是空的位置
        //不存在index
        if(index<0||index>size()){
            throw new AddIndex();
        }
        else {
            //在第一个位置
            if(index==0){
                //忽略了在首位置插入
                //head.val=data;
                addLast(data);
                return true;
            }else {
                //存在其他位置
                List node=new List(data);
                List cur=head;
                for (int i = 1; i < index; i++) {
                    cur=cur.next;
                }
                node.next=cur.next;
                cur.next=node;
                return true;
            }
            
        }
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        List cur =this.head;
        for (int i = 0; i < size(); i++) {
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        //删除头节点
        if(this.head.val==key){
            this.head=this.head.next;
            return;
        }
        //如果是空链接
        if(head==null){
            return;
        }
        List cur =head;
        //找位置
        while(cur.next.val!=key){
            cur=cur.next;
            if(cur==null){
                System.out.println("不存在这个数字");
                return;
            }
        }
        //
        cur.next=cur.next.next;
    }
    //删除所有值为key的节点
    //忽略头节点，忽略连续的key
//    public void removeAllKey(int key){
//        List cur=this.head;
//        for (int i = 0; i < size(); i++) {
//            if(cur.next.val==key){
//                cur.next=cur.next.next;
//                i++;
//            }
//            cur=cur.next;
//
//        }
//    }
    public void removeAllKey(int key) {
        if(head==null){
            return;
        }
        List ret=head;
        List cur=head.next;
        while (cur!=null){
            if(cur.val==key){
                ret.next=cur.next;
                cur=cur.next;
            }else{
                ret=cur;
                cur=cur.next;
            }
        }
        if(head.val==key){
            head=head.next;
        }
    }
        //得到单链表的长度
    public int size(){
        int sum=0;
        List cur=this.head;
        while(cur!=null){
            cur=cur.next;
            sum++;
        }
        return sum;
    }

    public void clear(){
        this.head=null;
    }

    public void display(){
        List cur=this.head;
        while(cur!=null){
            System.out.println(cur.val);
            cur=cur.next;
        }
    }
}
